import java.util.*;

public class InterviewQuestion {
    static class Node {
        public int val;
        public Node next;
        public Node random;

        public Node(int val) {
            this.val = val;
            this.next = null;
            this.random = null;
        }
    }

    public Node head;

    //随机链表的复制
    public Node copyRandomList(Node head) {
        Map<Node,Node> map = new HashMap<>();
        //第一次遍历，记录键值对，赋值
        Node cur = head;
        while (cur != null) {
            Node node = new Node(cur.val);
            map.put(cur,node);
            cur = cur.next;
        }
        //第二次遍历，根据键值对深拷贝
        cur = head;
        while (cur != null) {
            map.get(cur).next = map.get(cur.next);
            map.get(cur).random = map.get(cur.random);
            cur = cur.next;
        }
        return map.get(head);
    }

    //坏键盘打字问题
    public static void func(String str1, String str2) {
        str1 = str1.toUpperCase();
        str2 = str2.toUpperCase();
        Set<Character> set = new HashSet<>();
        //将set2中的字符串转化为字符存放在Set中
        for (char ch : str2.toCharArray()) {
            set.add(ch);
        }
        //遍历set1，看那个字符不在Set中
        Set<Character> setBroken = new HashSet<>();
        for (char ch : str1.toCharArray()) {
            //去重
            if (!set.contains(ch) && !setBroken.contains(ch)) {
                setBroken.add(ch);
                System.out.print(ch);
            }
        }
    }

    //宝石与石头
    public int numJewelsInStones(String jewels, String stones) {
        Set<Character> set = new HashSet<>();
        int count = 0;
        //把宝石放入集合
        for(char ch : jewels.toCharArray()) {
            set.add(ch);
        }
        //遍历石头
        for(char ch : stones.toCharArray()) {
            if(set.contains(ch)) {
                count++;
            }
        }
        return count;
    }

    //只出现一次的数字
    public int singleNumber(int[] nums) {
        Set<Integer> set = new HashSet<>();
        for(int i = 0; i < nums.length; i++) {
            if(!set.contains(nums[i])) {
                set.add(nums[i]);
            } else {
                set.remove(nums[i]);
            }
        }
        for(int i = 0; i < nums.length; i++) {
            if(set.contains(nums[i])) {
                return nums[i];
            }
        }
        return -1;
    }

    //存在重复元素
    public boolean containsDuplicate(int[] nums) {
        Set<Integer> set = new HashSet<>();
        for (int i = 0; i < nums.length; i++){
            if (set.contains(nums[i])) {
                return true;
            } else {
                set.add(nums[i]);
            }
        }
        return false;
    }

    //存在重复元素2
    public boolean containsNearbyDuplicate(int[] nums, int k) {
        Map<Integer,Integer> map = new HashMap<>();
        for(int i = 0; i < nums.length; i++) {
            if(map.containsKey(nums[i]) && i - map.get(nums[i]) <= k) {
                return true;
            }
            map.put(nums[i],i);
        }
        return false;
    }


    //前K个高频单词
    /*//创建一个比较器,小根堆
    class CmpKV implements Comparator<Map.Entry<String, Integer>> {
        public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {
            if (o1.getValue() == o2.getValue()) {
                return o2.getKey().compareTo(o1.getKey());//返回字典序
            } else {
                return o1.getValue() - o2.getValue();
            }
        }
    }

    class Solution {
        public List<String> topKFrequent(String[] words, int k) {
            //1.统计每个单词出现的频次
            Map<String,Integer> map = new HashMap<>();
            for(String s : words) {
                map.put(s, map.getOrDefault(s, 0) + 1);
            }
            //2.创建一个大小为 k 的堆
            //比较器
            PriorityQueue<Map.Entry<String, Integer>> heap = new PriorityQueue<>(new CmpKV());
            for(Map.Entry<String, Integer> hash : map.entrySet()) {
                heap.offer(hash);
                //当优先级队列中的元素大于 K 个时，删除堆顶元素
                //始终保持优先级队列中为 K 个元素
                if(heap.size() > k) {
                    heap.poll();
                }
            }
            //3.取堆中的前 k 个元素
            List<String> ret = new ArrayList<>(k);
            while(!heap.isEmpty()) {
                ret.add(heap.poll().getKey());
            }
            //从优先级队列中取出的元素是反的，需要逆置过来
            Collections.reverse(ret);
            return ret;
        }
    }*/


    //前K个高频单词
    public List<String> topKFrequent(String[] words, int k) {
        //1.统计每个单词出现的次数
        Map<String,Integer> map = new HashMap<>();
        for (String word : words) {
            if (map.get(word) == null) {
                map.put(word, 1);
            } else {
                map.put(word, map.get(word) + 1);
            }
        }
        //2.建立小根堆，指定比较的方式
        PriorityQueue<Map.Entry<String,Integer>> minHeap = new PriorityQueue<>(new Comparator<Map.Entry<String, Integer>>() {
            @Override
            public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {
                if (o1.getValue().compareTo(o2.getValue()) == 0) {
                    //按照字母顺序建立大根堆
                    return o2.getKey().compareTo(o1.getKey());
                }
                return o1.getValue() - o2.getValue();
            }
        });
        // 3.遍历map 调整优先级队列
        for (Map.Entry<String, Integer> entry : map.entrySet()) {
            if (minHeap.size() < k) {
                minHeap.offer(entry);
            } else {
                Map.Entry<String, Integer> top = minHeap.peek();
                // 如果当前频率相同
                if (top.getValue().compareTo(entry.getValue()) == 0) {
                    // 字母顺序小的进来
                    if (top.getKey().compareTo(entry.getKey()) > 0) {
                        // 出堆
                        minHeap.poll();
                        minHeap.offer(entry);
                    }
                } else {
                    if (top.getValue().compareTo(entry.getValue()) < 0) {
                        minHeap.poll();
                        minHeap.offer(entry);
                    }
                }
            }
        }
        List<String> ret = new ArrayList<>();
        for (int i = 0; i < k; i++) {
            Map.Entry<String,Integer> top = minHeap.poll();
            ret.add(top.getKey());
        }
        Collections.reverse(ret);
        return ret;
    }
}
